#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
		int lens = array.size();
		int ret = array[0];
		vector<int> dp(lens,0);
		dp[0] = array[0];
		for(int i = 1; i < lens; ++i){
			dp[i] = dp[i-1]<0?array[i]:dp[i-1] + array[i];
			ret = ret > dp[i]?ret:dp[i];
			cout << dp[i] << ",";
		}
		cout << endl;
		return ret;
	}
};

int main(){

	vector<int> array = {-2,-8,-1,-5,-9};

	Solution s;
	cout << s.FindGreatestSumOfSubArray(array) << endl;

	return 0;

}

